home *** CD-ROM | disk | FTP | other *** search
/ System Booster / System Booster.iso / Texteditors / Origami / bindings / fun / maze-mac < prev    next >
Encoding:
Text File  |  1996-09-27  |  9.8 KB  |  338 lines

  1. @if-using not(MAZE-MAC)
  2.   @use (MAZE-MAC)
  3.   @use (SHOW-PATH)            ; the current path is marked with o (SLOWER)
  4.   @if-using (SHOW-PATH)
  5.     ;@use (HIDE_SEARCH)         ; don't display the search, only the result
  6.   @fi
  7.   ;OCL{{{}}}
  8.   ;OCL{{{  description of the problem and its solution
  9.   ;OCL{{{  the algorithm
  10.   ; These macros 'solve' any maze produced by the a-maze-ing maze.c program.
  11.   ;
  12.   ; First, a bit of maze theory.
  13.   ; If you were put into a maze, a guaranteed method of finding your way
  14.   ; out of the maze is to put your left hand onto a wall and just keep walking,
  15.   ; never taking your hand off the wall. This technique is only guaranteed to
  16.   ; work if the maze does not have any 'islands', or if the 'exit' is on the
  17.   ; same island as your starting point. These conditions hold for the mazes
  18.   ; under consideration.
  19.   ;
  20.   ; Assuming that the maze is made up of horizontal and vertical walls spaced
  21.   ; one step apart and that you can move either north, south, east or west,
  22.   ; then you can automate this procedure by carrying out the following steps.
  23.   ;
  24.   ; 1. Put yourself somewhere in the maze near a wall.
  25.   ; 2. Check if you have a wall on your left. If so, go to step 4.
  26.   ; 3. There is no wall on your left, so turn on the spot to your left and step
  27.   ;    forward by one step and repeat step 2.
  28.   ; 4. Check what is directly in front of you. If it is a wall, turn on the
  29.   ;    spot to your right by 90 degrees and repeat step 4.
  30.   ; 5. There is no wall in front of you, so step forward one step and
  31.   ;    go to step 2.
  32.   ;OCL}}}
  33.   ;OCL{{{  the used maze-format
  34.   ; By examining a maze produced by the maze.c program you will see that
  35.   ; each square of the maze is one character high and two characters wide.
  36.   ; To go north or south, you move by a one character step, but to move east or
  37.   ; west you move by a two character step. Also note that in any position
  38.   ; there are four places where walls could be put - to the north, to the south,
  39.   ; to the east and to the west.
  40.   ; A wall exists to the north of you if the character to the north of
  41.   ; you is a _ (otherwise it is a space).
  42.   ; A wall exists to the east of you if the character to the east of you
  43.   ; is a | (otherwise it is a .).
  44.   ; A wall exists to the west of you if the character to the west of you
  45.   ; is a | (otherwise it is a .).
  46.   ; A wall exists to the south of you if the character where you are
  47.   ; is a _ (otherwise it is a space).
  48.   ;OCL}}}
  49.   ;OCL{{{  implementation
  50.   ; i implemented it with a couple of macros
  51.   ;    maze-step - do one of the above mentioned steps of
  52.   ;                the algorithm
  53.   ;    set-destination -
  54.   ;                check the current cursor-position to be a correct
  55.   ;                destination-point. (Its a little bit simple, if you
  56.   ;                are not in the maze, it will not work correct).
  57.   ;    get-new-maze -
  58.   ;                append at the end of ypur text a new maze.
  59.   ;                the command 'maze' must be available.
  60.   ;
  61.   ; all other macros are help-functions
  62.   ;
  63.   ; used variables:
  64.   ;   maze-dir: direction of movement
  65.   ;             0 - up
  66.   ;             1 - left
  67.   ;             2 - down
  68.   ;             3 - right
  69.   ;   maze-state: state of the machine like above
  70.   ;   maze-front: is set by front-wall, if there is a wall
  71.   ;OCL}}}
  72.   ;OCL{{{  how to do it
  73.   ; 0. Put the command maze in your path. This is the same a for vi and the
  74.   ;    used maze-format is the same too!
  75.   ; 1. put the following macros in your OCL-file and make a new .origamirc .
  76.   ; 2. Choose keybindings for the macros maze-step, get-new-maze, set-destination
  77.   ; 3. get a maze with get-new-maze
  78.   ; 4. go into the maze and set the destination with set-destination
  79.   ; 5. do maze-stepo and it runs!!!
  80.   ;OCL}}}
  81.   ;OCL}}}
  82.   ;OCL{{{  libs
  83.   @lib delchar
  84.   ;OCL}}}
  85.   ;OCL{{{  vars
  86.   ( defvar
  87.      ( maze-dir        ; direction to go
  88.        maze-front      ; what is in front of me
  89.        maze-x-pos      ; current cursor-position
  90.        maze-y-pos
  91.        maze-begin-line ; first state in the maze
  92.        maze-state      ; code the current state of the automata
  93.        maze-new-x-pos
  94.        maze-new-y-pos
  95.        go-line-arg-
  96.        x
  97.        case-0
  98.        case-1
  99.        case-2
  100.        case-3
  101.        case-4
  102.        case-5
  103.      )
  104.   )
  105.   ;OCL}}}
  106.   ;OCL{{{  help-functions
  107.   ;OCL{{{  turn-left
  108.   (deffun turn-left (
  109.     if =(maze-dir 0) (
  110.       set maze-dir 3
  111.     ) else (
  112.       set maze-dir +(maze-dir -1)
  113.     )fi
  114.    )
  115.   )
  116.   ;OCL}}}
  117.   ;OCL{{{  test-case
  118.   (deffun test-case (
  119.     set case-1 +(case-0 -1)
  120.     set case-2 +(case-0 -2)
  121.     set case-3 +(case-0 -3)
  122.     set case-4 +(case-0 -4)
  123.     set case-5 +(case-0 -5)
  124.   ))
  125.   ;OCL}}}
  126.   ;OCL{{{  front-wall
  127.   (deffun front-wall (
  128.     set maze-front 0
  129.     set case-0 maze-dir
  130.     test-case
  131.     case
  132.       ;OCL{{{  dir up
  133.       (=(case-0 0) (
  134.         previous-line
  135.         if or(test-char "_ test-char "O) (set maze-front 1) fi
  136.         next-line
  137.       ))
  138.       ;OCL}}}
  139.       ;OCL{{{  dir left
  140.       (=(case-1 0) (
  141.          backward-character
  142.          if test-char "| (set maze-front 1) fi
  143.          forward-character
  144.       ))
  145.       ;OCL}}}
  146.       ;OCL{{{  dir down
  147.       (=(case-2 0) (
  148.         if or(test-char "_  test-char "O) (set maze-front 1) fi
  149.       ))
  150.       ;OCL}}}
  151.       ;OCL{{{  dir right
  152.       (=(case-3 0) (
  153.         forward-character
  154.         if test-char "| (set maze-front 1) fi
  155.         backward-character
  156.       ))
  157.       ;OCL}}}
  158.       default (message-exit "incorrect_dir_in_front)
  159.     esac
  160.   ))
  161.   ;OCL}}}
  162.   ;OCL{{{  go
  163.   ;OCL{{{  go-line-
  164.   ( deffun go-line-
  165.      ( local
  166.         ( go-line-arg- )
  167.         ( while
  168.              pre
  169.               ( set x -(go-line-arg- store-line) )
  170.                 <>(x 0)
  171.              ;OCL{{{  one step to correct line
  172.              ( if >(x 0)
  173.                 ;OCL{{{  down
  174.                 ( if test-bottom
  175.                    ( @if-using (SCR-OFF)
  176.                        screen-on
  177.                        redraw-display
  178.                      @fi
  179.                      return-from-macro
  180.                    )
  181.                   fi
  182.                   next-line
  183.                 )
  184.                 ;OCL}}}
  185.                else
  186.                 ;OCL{{{  up
  187.                 ( if test-top ( return-from-macro ) fi
  188.                   previous-line
  189.                   ;OCL{{{  on fold?, maybe down again
  190.                   if or(test-fold-line,test-filed)
  191.                    ( set x -(go-line-arg- store-line)
  192.                      if =(x 0) ( return-from-macro ) fi
  193.                      ;OCL{{{  maybe skip to end of this fold
  194.                      if >(x 0)
  195.                       ( if test-filed ( return-from-macro ) fi
  196.                         open-fold
  197.                         mtool-bot
  198.                       )
  199.                      fi
  200.                      ;OCL}}}
  201.                    )
  202.                   fi
  203.                   ;OCL}}}
  204.                 )
  205.                 ;OCL}}}
  206.                fi
  207.              )
  208.              ;OCL}}}
  209.         )
  210.      )
  211.   )
  212.   ;OCL}}}
  213.   (deffun go (
  214.     set maze-x-pos store-pos
  215.     set maze-y-pos store-line
  216.       case
  217.         @if-using (SHOW-PATH)
  218.           (test-char "  ("o ))
  219.           (test-char "_ ("O ))
  220.         @fi
  221.         default (forward-character)
  222.       esac
  223.     backward-character
  224.     set case-0 maze-dir
  225.     test-case
  226.     case
  227.       (=(case-0 0) (previous-line))
  228.       (=(case-1 0) (backward-character backward-character))
  229.       (=(case-2 0) (next-line))
  230.       (=(case-3 0) (forward-character forward-character))
  231.       default (message-exit "incorrect_dir_in_go)
  232.     esac
  233.     @if-using (SHOW-PATH)
  234.     if or(test-char "o test-char "O) (
  235.       set maze-new-x-pos store-pos
  236.       set maze-new-y-pos store-line
  237.       set go-line-arg- maze-y-pos
  238.       go-line-
  239.       goto-counter maze-x-pos
  240.       case
  241.         (test-char "  ("o ))
  242.         (test-char "_ ("O ))
  243.         (test-char "o ("  ))
  244.         (test-char "O ("_ ))
  245.         default (message-exit "invalid_maze )
  246.       esac
  247.       set go-line-arg- maze-new-y-pos
  248.       go-line-
  249.       goto-counter maze-new-x-pos
  250.     ) fi
  251.     @fi
  252.   ))
  253.   ;OCL}}}
  254.   ;OCL}}}
  255.   ;OCL{{{  get new maze
  256.   (deffun get-new-maze (
  257.     beginning-of-fold
  258.     beginning-of-line
  259.     set maze-begin-line +(store-line  1)
  260.     next-line
  261.     pipe-from-command
  262.        "maze
  263.     newline-and-indent
  264.     message-exit "new_maze_read
  265.   ))
  266.   ;OCL}}}
  267.   ;OCL{{{  set-destination
  268.   (deffun set-destination (
  269.     if or(test-char "  ,test-char "_)
  270.       (delete-character "X )
  271.     else
  272.       (message-exit "no_correct_position)
  273.     fi
  274.   ))
  275.   ;OCL}}}
  276.   ;OCL{{{  maze-step
  277.   (deffun maze-step (
  278.     @if-using (HIDE_SEARCH) screen-off @fi
  279.     add-mode-overwrite
  280.     set maze-state 1
  281.     set maze-dir 0
  282.     if =(maze-begin-line 0) ( set maze-begin-line store-line ) fi
  283.     goto-line-counter maze-begin-line
  284.     search-forward "X newline-and-indent
  285.     if not(test-char "X) (message-exit "no_destination-point) fi
  286.     goto-line-counter maze-begin-line
  287.     search-forward "| newline-and-indent
  288.     forward-character
  289.     set maze-state 2
  290.     while not(test-char "X) (
  291.       show-cursor 0
  292.       set case-0 maze-state
  293.       test-case
  294.       case
  295.         ;OCL{{{  state 2
  296.         (=(case-2 0) (
  297.           turn-left
  298.           front-wall
  299.           repeat 3(turn-left)
  300.           if =(maze-front 0) (
  301.             set maze-state 3
  302.           ) else (
  303.             set maze-state 4
  304.           ) fi
  305.         ))
  306.         ;OCL}}}
  307.         ;OCL{{{  state 3
  308.         (=(case-3 0) (
  309.           turn-left
  310.           go
  311.           set maze-state 2
  312.         ))
  313.         ;OCL}}}
  314.         ;OCL{{{  state 4
  315.         (=(case-4 0) (
  316.           front-wall
  317.           if =(maze-front 0)
  318.             (set maze-state 5)
  319.           else
  320.             (repeat 3 (turn-left))
  321.           fi
  322.         ))
  323.         ;OCL}}}
  324.         ;OCL{{{  state 5
  325.         (=(case-5 0) (
  326.           go
  327.           set maze-state 2
  328.         ))
  329.         ;OCL}}}
  330.         default (message-exit "incorrect_maze_state)
  331.       esac
  332.     )
  333.     delete-mode-overwrite
  334.     @if-using (HIDE_SEARCH) screen-on redraw-display @fi
  335.   ))
  336.   ;OCL}}}
  337. @fi
  338.